0%

Self-Learned Algorithms - 08

Posted on Edited on In

Self-Learned Algorithms - 08

This is my learning note about algorithms.

Reference

231.2的幂

https://leetcode-cn.com/problems/power-of-two/

解法

  • 时间复杂度为$O(\log N)$的常规解法
1
2
3
4
5
if n == 0:
	return False
while n % 2 == 0:
  n /= 2
return n == 1
  • 位运算：时间复杂度$O(1)$。若$n = 2^x$且$x$为自然数（即$n$为2的幂），则一定满足以下条件：
    • 必要性：恒有n & (n - 1) == 0，这是因为$n$二进制最高位为1，其余所有位为0；$n - 1$二进制最高位为0，其余所有位为1。一定满足$n > 0$。
    • 充分性：n & n-1可以把$n$最低位的1变0，而当n & n-1 == 0时，则说明$n$只有一个1。
1
return n > 0 and n & (n - 1) == 0

191.位1的个数

https://leetcode-cn.com/problems/number-of-1-bits/

题解

解法

  • 位移：从最后一位往前遍历，检测当前探索数是否为1
1
2
3
4
5
6
count = 0
while (n != 0):
  if (n & 1 != 0):
  	count += 1
  n = n>>1
return count
  • n & (n - 1)可以消去n的二进制表示中最后一个1，其他的1都不会被影响
1
2
3
4
5
count = 0
while (n != 0):
  n = n & (n - 1)
  count += 1
return count

136.只出现一次的数字

https://leetcode-cn.com/problems/single-number/

题解

  • 不考虑复杂度的话方法有很多：哈希表储存数字和出现次数、集合储存数字并删掉出现过的数字、集合储存出现过的数字并用出现过数字的两倍减去原数组中数字之和……

解法

  • 位运算：异或运算$\oplus$。利用异或运算的性质：
    • 任何数和0做异或运算，结果仍然是原来的数，即$a \oplus 0=a$。
    • 任何数和其自身做异或运算，结果是0，即$a \oplus a=0$。
    • 异或运算满足交换律和结合律，即$a \oplus b \oplus a=b \oplus a \oplus a=b \oplus (a \oplus a)=b \oplus0=b$。
1
return reduce(lambda x, y: x ^ y, nums)
  • 数学：二倍出现的数字减去原数组之和
1
return sum(set(nums))*2-sum(nums)

137.只出现一次的数字2

https://leetcode-cn.com/problems/single-number-ii/

题解

  • 136题的延续，同样是哈希、位运算、数学计算都可以解决的

解法

  • 数学：三倍出现的数字减去原数组之和为所求之数的二倍
1
return (3 * sum(set(nums)) - sum(nums)) // 2
  • 哈希表
1
2
3
4
hashmap = Counter(nums)
for k in hashmap.keys():
  if hashmap[k] == 1:
  	return k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 解法1
ones, twos = 0, 0
for num in nums:
  ones = ones ^ num & ~twos
  twos = twos ^ num & ~ones
return ones

# 解法2
seen_once = seen_twice = 0
for num in nums:
  # first appearance: 
  # add num to seen_once 
  # don't add to seen_twice because of presence in seen_once

  # second appearance: 
  # remove num from seen_once 
  # add num to seen_twice

  # third appearance: 
  # don't add to seen_once because of presence in seen_twice
  # remove num from seen_twice
  seen_once = ~seen_twice & (seen_once ^ num)
  seen_twice = ~seen_once & (seen_twice ^ num)

return seen_once

268.缺失数字

https://leetcode-cn.com/problems/missing-number/

解法

  • 排序，对照下标找出缺失
1
2
3
4
5
nums.sort()
for i in range(len(nums)):
  if nums[i] != i:
    return i
return len(nums)
  • 哈希表
1
2
3
4
5
num_set = set(nums)
n = len(nums) + 1
for number in range(n):
  if number not in num_set:
  	return number
  • 位运算
1
2
3
4
missing = len(nums)
for i, num in enumerate(nums):
	missing ^= i ^ num
return missing
  • 数学法：数列求和减去数组之和，但有溢出的风险
1
2
3
4
5
6
7
8
9
expected_sum = len(nums)*(len(nums)+1)//2
actual_sum = sum(nums)
return expected_sum - actual_sum

# 避免溢出可以边求和边利用索引值
res = len(nums)
for idx, num in enumerate(nums):
  res += idx - num
return res